https://leetcode-cn.com/problems/3sum/

错误解法，超时

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        #排序
        nums.sort()
        ret = []
        for i in range(0, len(nums) - 2):
            #nums[i]不可能大于0
            if nums[i] > 0:
                break
            for j in range(i + 1, len(nums) - 1):
                #值不可能存在，跳出
                if nums[i] + nums[j] > 0:
                    break
                #当前ij的值已存在，跳出
                if ret != [] and (nums[i],nums[j]) in [x[:2] for x in ret]:
                    continue
                val = abs(nums[i] + nums[j])
                for k in range(j + 1, len(nums)):
                    if val == nums[k]:
                        ret.append((nums[i],nums[j],nums[k]))
                        break
        return ret

正确解法:

1. 先确定第一个合法数字，不能为>0的数。
2. 判断是否和上一位相同，若相同代表已经判断过，跳出。
3. 从当前位置的下一位和列表末尾向中间逼近，通过判断三个数的和确定是左侧还是右侧向中间移动，直到left=right
4. 判断成功后，如果发现下一位与当前位置相同，则跳过。

时间复杂度：Oleft(n^{2}right)O(n
2
)，数组排序 O(N log N)O(NlogN)，遍历数组 Oleft(nright)O(n)，双指针遍历 Oleft(nright)O(n)，总体 O(N log N)+Oleft(nright)*Oleft(nright)O(NlogN)+O(n)∗O(n)，Oleft(n^{2}right)O(n
2
)
空间复杂度：O(1)O(1)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        #排序
        nums.sort()
        #返回值
        ret = []
        lenNums = len(nums)
        for i in range(lenNums):
            val = nums[i]
            #i的值>0 无解
            if val > 0:
                break
            #判断是否和上一位重复
            if i > 0 and val == nums[i-1]:
                continue
            l = i + 1
            r = lenNums - 1
            while l < r:
                #末位<0 无解
                if nums[r] < 0:
                    break
                if val + nums[l] + nums[r] == 0:
                    ret.append((
                        val , nums[l] , nums[r]
                    ))
                    #判断下一位是否和当前相同，若相同则跳过
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    #寻找下一个
                    r -= 1
                    l += 1
                elif val + nums[l] + nums[r] > 0:
                    #当前值偏大，右侧想左移动
                    r -= 1
                else:
                    #当前值偏小，左侧向右移动
                    l += 1
        return ret